White's Studio.

Lintcode- 562.Backpack IVFollow

LintCode
2018/08/24 Share

Lintcode- 562.Backpack IVFollow

Description

Given n items with size nums[i] which an integer array and all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

1
Each item may be chosen unlimited number of times

Have you met this question in a real interview? Yes

Problem Correction

Example

Given candidate items [2,3,6,7] and target 7,

1
2
3
A solution set is: 
[7]
[2, 2, 3]

return 2

Analyst

  1. 最后一步

    F[n][m]表示前 n个有 多少种方式拼出m

    最后一个选上：F[n][m] = Sum(F[n-1][m-A[ki]])

    最后一个不选上：F[n][m] = F[n-1][m]

  2. 顺序从小到大

  3. 边界情况

    F[k][0] = 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackIV(int[] nums, int target) {
        // write your code here
        int len = nums.length;
        if (len == 0) return 0;
        
        int[][] F = new int[len+1][target+1];
        
        
        for (int i = 0; i <= len; i++) {
            F[i][0] = 1;
        }
        
        for (int i = 1; i <= len; i++ ) {
            int item = nums[i-1];
            for (int k = 1; k <= target; k++) {
                F[i][k] = F[i-1][k];
                if (k >= item) {
                    F[i][k] += F[i][k - item];
                }
            }
        }
        
       
        return F[len][target];
    }
}

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/08/24/LintCode-562.Backpack IVFollow/

发表日期: August 24th 2018, 1:22:18

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Lintcode- 562.Backpack IVFollow
    1. 1.0.1. Description
    2. 1.0.2. Example
    3. 1.0.3. Analyst
    4. 1.0.4. Code
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm